填充
题目 填充
思路分析
贪心问题也可以从集合去考虑
将一个问题划分成多个子集 若答案一定会出现在某个集合中 那么就用贪心 若要由多个集合综合而来 就需要用dp
若是贪心问题 直接将集合缩小成某个子集即可 类似于二分 抛开另一边不用管了
在1110中 111能组成一种情况
这种情况一定会被11替换
所以只需要考虑相邻的两个数是否配对 若配对 跳过已配对里的第二个数 直接看它后面的数是否又与i+1配对
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s;
int main()
{
cin>>s;
int res=0;
for(int i=0;i+1<s.size();i++){
if(s[i]==s[i+1] || s[i]=='?' || s[i+1]=='?'){
res++;
i++; //1110中 前两个11已配对 就无需考虑后两个11是否配对 它们属于同一种情况 直接看第三个1和第四个0是否配对
}
}
cout<<res;
return 0;
}
💬 评论